import random


class SwapSort:
    """
    交换排序类，包含冒泡排序和快速排序算法的实现。
    """

    @staticmethod
    def bubble_sort(arr):
        """
        冒泡排序算法的核心思想是通过重复交换相邻的元素，将较大的元素逐步向右移动到正确的位置。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        是稳定排序算法。
        原因：冒泡排序中，只有当相邻的元素大小不同时才进行交换，因此相同元素的相对顺序不会改变。
        """
        n = len(arr)

        # 步骤 1: 外层循环控制比较的轮数
        for i in range(n):
            # 步骤 2: 内层循环进行相邻元素的比较与交换
            for j in range(n - 1):
                if arr[j] > arr[j + 1]:
                    # 步骤 3: 交换元素
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]

        return arr


    @staticmethod
    def quick_sort(arr):
        """
        快速排序算法的核心思想是通过选择一个基准元素，将数组划分为左右两个子数组，并递归地对子数组进行排序。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        不是稳定排序算法。
        原因：快速排序中，元素的交换是基于基准元素的大小关系进行的，相同元素可能会交换位置，导致相对顺序改变。
        """
        def partition(arr, low, high):
            """
            根据基准元素将数组进行划分，并返回基准元素的最终位置。

            参数：
            arr (list): 待划分的列表。
            low (int): 子数组的起始索引。
            high (int): 子数组的结束索引。

            返回：
            int: 基准元素的最终位置。
            """
            pivot = arr[high]
            i = low - 1

            for j in range(low, high):
                if arr[j] <= pivot:
                    i += 1
                    # 步骤 3: 交换元素
                    arr[i], arr[j] = arr[j], arr[i]

            # 步骤 4: 将基准元素放置到最终位置
            arr[i + 1], arr[high] = arr[high], arr[i + 1]
            return i + 1

        def quick_sort_helper(arr, low, high):
            if low < high:
                # 步骤 1: 根据基准元素划分数组
                pi = partition(arr, low, high)
                
                # 步骤 2: 递归地对子数组进行排序
                quick_sort_helper(arr, low, pi - 1)
                quick_sort_helper(arr, pi + 1, high)

        n = len(arr)
        quick_sort_helper(arr, 0, n - 1)
        return arr



# 主程序
if __name__ == "__main__":
    # 生成随机输入列表
    input_list = random.sample(range(1, 101), 10)
    print("随机输入列表:", input_list)

    # 创建 SwapSort 对象
    sorter = SwapSort()

    # 调用冒泡排序方法进行排序
    sorted_list_bubble = sorter.bubble_sort(input_list)
    # 输出结果
    print("冒泡排序后的列表:", sorted_list_bubble)  # 冒泡排序后的列表: [1, 2, 4, 5, 7]

    # 调用快速排序方法进行排序
    sorted_list_quick = sorter.quick_sort(input_list)
    # 输出结果
    print("快速排序后的列表:", sorted_list_quick)  # 快速排序后的列表: [1, 2, 4, 5, 7]
